from collections import deque

# 项目任务类
class ProjectTask:
    def __init__(self, id: int, t: int) -> None:
        self.id = id # 编号
        self.time = t # 完成需时
        self.indegree = 0 # 入度
        self.nextTasks = [] # 后置任务
        self.startTime = 0 # 最早开始时间

# 任务列表，用数组表示
tasks: list[ProjectTask] = []

# 维护当前DFS正在处理中的顶点
process = set()

# 返回以起点a出发可以到达的所有邻接点
def next(a: int) -> list[int]:
    for t in tasks[a].nextTasks:
        yield t.id

# 回溯法寻找有向图中的回退边
# 如果找到回退边返回true，否则返回false
def dfs(s: int) -> bool: 
    # 判断回退边的根据：搜索到一个顶点已经存在于递归搜索当中
    if s in process:
        return True

    # 将当前顶点新加入进dfs搜索顶点
    process.add(s)

    # 搜索下一个顶点
    for t in next(s): 
        # 递归，而且如果在递归搜索中找到回退边，就可以直接返回
        if dfs(t):
            return True

    # 记得把搜索完毕的顶点从搜索列表中移除
    process.remove(s)
    return False

# 分支限界法进行任务编排
def bfs():
    queue = deque()
    for t in tasks:
        if t.indegree == 0:
            queue.append(t)
    i = 1
    while queue:
        st = queue.popleft()
        print('#%d %d %d' % (i, st.id, st.startTime))
        i += 1
        for t in st.nextTasks:
            # 更新完成时间及入度，如果入度为0，加入队列
            t.startTime = max(t.startTime, st.startTime + st.time)
            t.indegree -= 1
            if t.indegree == 0:
                queue.append(t)

# 项目任务编排    
def projectPlan(n: int, times: list[int], edges: list[list[int]]):
    global tasks
    # 构建图数据结构
    tasks = [ProjectTask(i, times[i]) for i in range(n)]
    for a, b in edges:
        tasks[a].nextTasks.append(tasks[b])
        tasks[b].indegree += 1

    # 先执行DFS确认任务的合理性
    for task in tasks:
        if task.indegree == 0:
            if dfs(task.id):
                print('任务不合理，存在回退边！')
                return

    # 没问题则执行bfs
    bfs()

# main
n = 10
times = [ 0, 2, 2, 1, 4, 5, 1, 6, 4, 0 ]
edges = [[0, 1], [0, 4], [1, 2], [1, 3], [2, 5], [3, 6], [4, 6], [5, 7], [5, 8], [6, 8], [7, 9], [8, 9]]
projectPlan(n, times, edges)